<?php
/**
 * @title 75. 颜色分类 - 单指针2次遍历
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class Solution {

    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function sortColors(&$nums) {
        /**
         * @since 2020-10-12 指针位置
         */
        $p = 0;

        /**
         * @since 2020-10-12 第1次遍历, 所有0放在头部
         */
        for($i=0, $len=count($nums); $i<$len; $i++){
            if($nums[$i] == 0){
                /**
                 * @since 2020-10-12 直接交换即可
                 * @since 2020-10-13 [1,0,0,0,0,0], 从i=1开始, 每个都进行1次if判断, 再交换, 最坏情况下耗时增加, 不如直接交换
                 */
                // if($i !== $p){
                    $nums[$i] = $nums[$p];
                    $nums[$p] = 0;
                // } else {}

                /**
                 * @since 2020-10-12 指针+1
                 */
                $p++;
            } else {}
        }

        /**
         * @since 2020-10-12 第2次遍历, 所有1放在0之后
         */
        for($i=$p; $i<$len; $i++){
            if($nums[$i] == 1){
                /**
                 * @since 2020-10-12 交换
                 */
                // if($i !== $p){
                    $nums[$i] = 2;
                    $nums[$p] = 1;
                // } else {}

                /**
                 * @since 2020-10-12 指针+1
                 */
                $p++;
            } else {}
        }

        /**
         * @return
         */
        return $nums;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.05_4.php
 */
$datas = [
    [2,0,2,1,1,0],
    [1,2,2,2,2,0,0,0,1,1],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->sortColors($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
